//
// Created by yubin on 2021/3/29.
//
#include <cstring>
#include <iostream>

#include "sqlist.h"

using std::cout;
using std::endl;

namespace sl {
    void InitList(SqList &L) {
        L.capacity = INIT_SIZE;
        L.length = 0;
        L.data = new ElemType[INIT_SIZE];
    }

    void DestroyList(SqList &L) {
        delete[] L.data;
        L.data = nullptr;
        L.capacity = 0;
        L.length = 0;
    }

    /**
     * 扩容
     */
    void expand(SqList &L) {
        // 检查是否需要扩容
        if (L.length < L.capacity)
            return;
        // 将数据移入新空间
        auto newData = new ElemType[L.capacity * 2];
        memcpy(newData, L.data, sizeof(ElemType) * L.length);
        // 交接数据空间
        delete[] L.data;
        L.data = newData;
        L.capacity *= 2;
    }

    /**
     * 在顺序表 L 的第 i 个位置插入新元素 e
     */
    bool ListInsert(SqList &L, int i, ElemType e) {
        // 判断 i 的范围是否有效
        if (i < 1 || i > L.length + 1) {
            return false;
        }
        // 判断存储空间是否已满
        if (L.length >= L.capacity) {
            expand(L);
        }
        // 把第 i 个及之后的元素后移一格
        for (int j = L.length; j >= i; j--) {
            L.data[j] = L.data[j - 1];
        }
        // 填入新元素
        L.data[i - 1] = e;
        L.length++;
        return true;
    }

    /**
     * 删除 L 中的第 i 个位置的元素，用引用变量 e 返回
     */
    bool ListDelete(SqList &L, int i, ElemType &e) {
        // 判断 i 的范围是否有效
        if (i < 1 || i > L.length) {
            return false;
        }
        // 赋给返回引用变量 e
        e = L.data[i - 1];
        // 将第 i 个位置后的元素前移一格
        for (int j = i; j < L.length; j++) {
            L.data[j - 1] = L.data[j];
        }
        L.length--;
        return true;
    }

    /**
     * 在顺序表 L 中查找第一个元素值等于 e 的元素，并返回其位序
     */
    int LocateElem(SqList &L, ElemType e) {
        // 顺序遍历对比
        for (int i = 0; i < L.length; i++) {
            if (L.data[i] == e) {
                return i + 1;
            }
        }
        return 0;
    }

    void PrintList(SqList const& L) {
        cout << "[";
        for (int i = 0; i < L.length - 1; i++) {
            cout << L.data[i] << ", ";
        }
        cout << L.data[L.length - 1] << ']';
    }

    int Length(SqList &L)
    {
        return L.length;
    }

    bool Empty(SqList &L)
    {
        return L.length == 0;
    }

    ElemType GetElem(SqList &L, int i)
    {
        return L.data[i - 1];
    }
}